#define quickread
#ifdef quickread
#include <cstdio> 
template <typename T>
inline void read(T& x)
{
    int c=getchar(), f=1; x=0;
    while(c<'0'||'9'<c) {if(c=='-') f=-1; c=getchar();}
    while('0'<=c&&c<='9') 
        x=(x<<3)+(x<<1)+c-'0', c=getchar();
    x*=f;
}
template <typename T>
inline void quickwrite(T x)
{
    if(x<0) putchar('-'), x*=-1;
    if(x>=10) quickwrite(x/10);
    putchar(x%10+'0');
}
#else 
#include <iostream>
#endif
#include <cstring>
#include <algorithm>
using namespace std;
#define DEBUG
const int N=1e6+10;
int n, k, q, tcnt; 
char s[N];
char t[N];
int nxt[N][26]; //nxt[i][c]:位置i之后，第一次出现字符c的位置，没有则为n+1
int d[N]; //d[i]:从位置i开始，需要添加的最少字符数，d[i]=d[mx]+1,mx是i之后所有字符的下一个位置的最大值
void init()
{
    read(n), read(k);
    scanf("%s", s);
    for(int i=0; i<=n+1; i++)
        for(int j=0; j<k; j++)
            nxt[i][j]=n;
    
    memset(d, 0, sizeof d);
    for(int i=n-1; i>=0; i--)
    {
        memcpy(nxt[i], nxt[i+1], sizeof nxt[i]); //nxt[i]=nxt[i+1]
        // printf("nxt[i+1]:"); for(int j=0; j<26; j++) printf("%d ", nxt[i+1][j]); puts("");
        // printf("  nxt[i]:"); for(int j=0; j<26; j++) printf("%d ", nxt[i][j]); puts("");

        int mx=0;
        for(int j=0; j<k; j++) mx=max(mx, nxt[i][j]);
        d[i]=d[mx]+1;
        nxt[i][s[i]-'a']=i;
    }
}

void solve()
{
    scanf("%s", t);
    int pos=-1;
    // for(int i=0; i<n; i++) printf("%d ", d[i]); puts("");
    for(int i=0; i<strlen(t); i++)
        pos=nxt[pos+1][t[i]-'a']; //找到s中能匹配的最远位置pos
    quickwrite(d[pos]);puts("");
}

// #undef DEBUG
signed main()
{
    #ifdef DEBUG
        freopen("../in.txt", "r", stdin);
        // freopen("../out.txt", "w", stdout);
    #endif
    #ifndef quickread
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #endif
    init();
    int T=1; scanf("%d", &T);
    while(T--) 
    {
        solve();
    }
    return 0;
}
